/*
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

bool isValid(string s)
{
    if (s.size() <= 1) {
        return false;
    }
    stack<char> stk;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(' || s[i] == ')'
            || s[i] == '[' || s[i] == ']'
            || s[i] == '{' || s[i] == '}') {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
                stk.push(s[i]);
                continue;
            }
            if (!stk.empty()
                && ((stk.top() + 1 == s[i]) || (stk.top() + 2 == s[i]))) {
                stk.pop();
            } else {
                return false;
            }
        }
    }
    if (stk.empty()) {
        return true;
    }
    return false;
}

int main(int argc, const char * argv[])
{
    cout<<isValid("){")<<endl;
    return 0;
}
